
//
// Authors:
//   Atsushi Enomoto
//
// Copyright 2007 Novell (http://www.novell.com)
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
// 
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
#if NET_2_0

using System;
using System.Collections;
using System.Collections.Generic;

namespace System.Xml.Linq
{

	public sealed class XNodeDocumentOrderComparer : IComparer, IComparer<XNode>
	{

		public XNodeDocumentOrderComparer()
		{
		}
		enum CompareResult
		{
			Same,
			Random,
			Parent,
			Child,
			Ancestor,
			Descendant,
			Preceding,
			Following
		}

		public int Compare(XNode x, XNode y)
		{

			switch (CompareCore(x, y))
			{

				case CompareResult.Same:
					return 0;

				case CompareResult.Random:
					return DateTime.Now.Ticks % 2 == 1 ? 1 : -1;

				case CompareResult.Parent:

				case CompareResult.Ancestor:

				case CompareResult.Preceding:
					return 1;
				default:
					return -1;
			}
		}
		CompareResult CompareCore(XNode n1, XNode n2)
		{
			if (n1 == n2)
				return CompareResult.Same;
			if (n1.Owner == null)
			{
				if (n2.Owner == null)
					// n1 and n2 do not share the same
					// top-level node, so return semi-
					// random value.
					return CompareResult.Random;
				CompareResult result = CompareCore(n1, n2.Owner);

				switch (result)
				{

					case CompareResult.Same:
						return CompareResult.Child;

					case CompareResult.Child:

					case CompareResult.Descendant:
						return CompareResult.Descendant;

					case CompareResult.Parent:

					case CompareResult.Ancestor:
						throw new Exception("INTERNAL ERROR: should not happen");
					default:
						return result;
				}
			}
			// else
			if (n2.Owner == null)
			{
				// do reverse
				CompareResult rev = CompareCore(n2, n1);

				switch (rev)
				{

					case CompareResult.Parent:
						return CompareResult.Child;

					case CompareResult.Child:
						return CompareResult.Parent;

					case CompareResult.Ancestor:
						return CompareResult.Descendant;

					case CompareResult.Descendant:
						return CompareResult.Ancestor;

					case CompareResult.Following:
						return CompareResult.Preceding;

					case CompareResult.Preceding:
						return CompareResult.Following;

					case CompareResult.Same:

					case CompareResult.Random:
						return rev;
				}
			}
			// both have parents
			CompareResult ret = CompareCore(n1.Owner, n2.Owner);

			switch (ret)
			{

				case CompareResult.Same:
					// n1 and n2 are sibling each other.
					return CompareSibling(n1, n2, CompareResult.Same);

				case CompareResult.Child:
					return CompareSibling(n1, n2.Owner, CompareResult.Child);

				case CompareResult.Parent:
					return CompareSibling(n1.Owner, n2, CompareResult.Parent);

				case CompareResult.Descendant:

					for (XNode i2 = n2; ; i2 = i2.Owner)
						if (i2.Owner == n1.Owner)
							return CompareSibling(n1, i2, CompareResult.Descendant);

				case CompareResult.Ancestor:

					for (XNode i1 = n1; ; i1 = i1.Owner)
						if (i1.Owner == n2.Owner)
							return CompareSibling(i1, n2, CompareResult.Ancestor);
				default:
					return ret;
			}
		}
		// results are returned as following/preceding, as it is also
		// used for comparing parents.
		CompareResult CompareSibling(XNode n1, XNode n2, CompareResult forSameValue)
		{
			if (n1 == n2)
				return forSameValue;

			for (XNode n = n1.NextNode; n != null; n = n.NextNode)
				if (n == n2)
					return CompareResult.Following;
			return CompareResult.Preceding;
		}
		int IComparer.Compare(object n1, object n2)
		{
			return Compare((XNode)n1, (XNode)n2);
		}
	}
}

#endif